package dp;

import java.util.ArrayList;
import java.util.List;

/**
 * 动态规划
 */
public class NewCoder_CC31 {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        /**
         * 思路一
         * 状态：F(i,j):从(0,0)到(i,j)的最短路径和
         * 状态转移方程：F(i,j)=Math.min(F(i-1,j-1),F(i-1,j))+triangle[i][j]
         * 初始状态：F(0,0)=triangle(0,0)
         * 返回结果：Math.min(row-1，i)
         */
        if(triangle.isEmpty()){
            return 0;
        }
        List<List<Integer>> minPathSum=new ArrayList<>();
        for (int i = 0; i < triangle.size(); i++) {
            minPathSum.add(new ArrayList<>());
        }
        minPathSum.get(0).add(triangle.get(0).get(0));
        for (int i = 1; i <triangle.size() ; i++) {
            int curSum=0;
            for (int j = 0; j <= i; j++) {
                if(j==0){
                    curSum=minPathSum.get(i-1).get(0)+triangle.get(i).get(j);
                }else if(j==i){
                    curSum=minPathSum.get(i-1).get(j-1)+triangle.get(i).get(j);
                }else {
                    curSum=Math.min(minPathSum.get(i-1).get(j-1),minPathSum.get(i-1).get(j))+triangle.get(i).get(j);
                }
                minPathSum.get(i).add(curSum);
            }
        }
        int size=triangle.size();
        int allMin=minPathSum.get(size-1).get(0);
        for (int i =1 ; i <size ; i++) {
            allMin=Math.min(minPathSum.get(size-1).get(i),allMin);
        }
        return allMin;

        /**
         * 思路二
         * 状态：F(i,j):到最后一行的最短路径和
         * 状态转移方程：F(i,j)=Math.min(F(i+1,j+1),F(i+1,j))+triangle[i][j]
         * 初始状态：F(n-1,0)=triangle(n-1,n-1)
         * 返回结果：F(0,0)
         */
//        if(triangle.isEmpty()){
//            return 0;
//        }
//        ArrayList<ArrayList<Integer>>  minPathSum=new ArrayList<>(triangle);
//        int row=minPathSum.size();
//        for (int i = row-2; i >=0 ; i--) {
//            for (int j = 0; j <= i; j++) {
//                int curSum=Math.min(triangle.get(i+1).get(j+1),triangle.get(i+1).get(j))+triangle.get(i).get(j);
//                minPathSum.get(i).set(j,curSum);
//            }
//        }
//        return minPathSum.get(0).get(0);
    }
}
